package J3_29;

public class test {
    //给你一个下标从 0 开始的整数数组 nums 。
    //
    //如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：
    //
    //i < j < k
    //nums[i] < nums[j] 且 nums[k] < nums[j]
    //请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。
    //
    //
    public int minimumSum1(int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] < nums[j] && nums[j] > nums[k])
                        min = Math.min(min, nums[i] + nums[j] + nums[k]);
                }
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    public static int minimumSum(int[] nums) {
        int len = nums.length;
        int[] left = new int[len];
        int min = Integer.MAX_VALUE;
        int ret = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            left[i] = min = Math.min(nums[i], min);
        }
        int right = nums[len - 1];
        for (int i = len - 2; i >= 1; i--) {
            if (nums[i] > left[i - 1] && nums[i] > right){
                ret = Math.min(ret, left[i - 1] + nums[i] + right);
            }
            right = Math.min(right, nums[i]);
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{8,6,1,5,3};

        System.out.println(minimumSum(arr));
    }
    }
